package leetcode_1_200;

import node.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_113 {
    public static void main(String[] args) {
/*        ArrayList<Object> l1 = new ArrayList<>();
        l1.add(1);
        ArrayList<Object> l2 = new ArrayList<>(l1);
        l1.add(22);
        System.out.println(l2);*/
        System.out.println(pathSum(new TreeNode(1, new TreeNode(2), new TreeNode(3)), 4));
    }
    private static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null)
            return ans;
        f(ans, new ArrayList<>(), root, targetSum, 0);
        return ans;
    }
    private static void f(List<List<Integer>> ans,List<Integer> list, TreeNode node, int targetSum, int sum){
        sum += node.val;
        list.add(node.val);
        if (node.left == null && node.right == null && sum == targetSum){
            ans.add(list);
        }
        if (node.left != null){
            f(ans, new ArrayList<>(list), node.left, targetSum, sum);
        }
        if (node.right != null){
            f(ans, list, node.right, targetSum, sum);
        }
    }
}
